package kmp;

import java.util.HashMap;

/**
 * 给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。
 * 如果是，返回 true ；否则，返回 false 。
 * 换句话说，s1 的排列之一是 s2 的 子串 。
 */
public class leetCode567_checkInclusion {
    public boolean checkInclusion(String s1, String s2) {
        if(s1 == null || s2 == null){
            return false;
        }
        if(s1.length() > s2.length()){
            return false;
        }

        HashMap<Character,Integer> need = new HashMap<>();
        HashMap<Character,Integer> window  = new HashMap<>();

        int n = s1.length();
        for (int i = 0; i < n; i++) {
            Character c = s1.charAt(i);
            need.put(c,need.getOrDefault(c,0) + 1);
        }


        int m = s2.length();
        int left = 0;
        int right = 0;
        int valid = 0;

        while (right < m){
            Character d = s2.charAt(right);
            right++;
            if(need.containsKey(d)){
                window.put(d,window.getOrDefault(d,0) + 1);
                if(window.get(d).equals(need.get(d))){
                    valid++;
                }
            }
            while (right - left >= n){
                if(valid == need.size()){
                    return true;
                }
                Character e = s2.charAt(left);
                left++;

                if(need.containsKey(e)){

                    if(window.containsKey(e)){
                        if(window.get(e).equals(need.get(e))){
                            valid--;
                        }
                        window.put(e,window.get(e) - 1);
                    }

                }

            }


        }
        return false;

    }
}
